Grokking Microsoft Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Microsoft Easy Problems
Buddy Strings (easy)
Solution: Buddy Strings
Can Place Flowers (easy)
Solution: Can Place Flowers
Reverse a LinkedList (easy)
Solution: Reverse a LinkedList
Maximum Number of Balloons (easy)
Solution: Maximum Number of Balloons
Binary Tree Path Sum (easy)
Solution: Binary Tree Path Sum
Pair with Target Sum (easy)
Solution: Pair with Target Sum
Buy Two Chocolates (easy)
Solution: Buy Two Chocolates
Root Equals Sum of Children (easy)
Solution: Root Equals Sum of Children
Excel Sheet Column Title (easy)
Solution: Excel Sheet Column Title
Merge Strings Alternately (easy)
Solution: Merge Strings Alternately
Min Cost Climbing Stairs (easy)
Solution: Min Cost Climbing Stairs
Plus One (easy)
Solution: Plus One
Intersection of Two Arrays (easy)
Solution: Intersection of Two Arrays
Find the Index of the First Occurrence in a String (easy)
Solution: Find the Index of the First Occurrence in a String
Merge Two Sorted Lists (easy)
Solution: Merge Two Sorted Lists
Nth Digit (medium)
Solution: Nth Digit
Restore IP Addresses (medium)
Solution: Restore IP Addresses
Find Original Array From Doubled Array (medium)
Solution: Find Original Array From Doubled Array
Reverse Words in a String II (medium)
Solution: Reverse Words in a String II
Longest Arithmetic Subsequence (medium)
Solution: Longest Arithmetic Subsequence
Matchsticks to Square (medium)
Solution: Matchsticks to Square
Score of Parentheses (medium)
Solution: Score of Parentheses
Maximum Length of a Concatenated String with Unique Characters (medium)
Solution: Maximum Length of a Concatenated String with Unique Characters
Inorder Successor in BST (medium)
Solution: Inorder Successor in BST
Distribute Coins in Binary Tree (medium)
Solution: Distribute Coins in Binary Tree
Spiral Matrix (medium)
Solution: Spiral Matrix
Delete Node in a BST (medium)
Solution: Delete Node in a BST
Sum of Subarray Minimums (medium)
Solution: Sum of Subarray Minimums
Rotate Image (medium)
Solution: Rotate Image
Combinations (medium)
Solution: Combinations
Maximum Level Sum of a Binary Tree (medium)
Solution: Maximum Level Sum of a Binary Tree
Multiply Strings (medium)
Solution: Multiply Strings
Best Time to Buy and Sell Stock II (medium)
Solution: Best Time to Buy and Sell Stock II
Largest Palindromic Number (medium)
Solution: Largest Palindromic Number
Remove Duplicate Letters (medium)
Solution: Remove Duplicate Letters
Next Permutation (medium)
Solution: Next Permutation
132 Pattern (medium)
Solution: 132 Pattern
Valid Sudoku (medium)
Solution: Valid Sudoku
Number of Islands (medium)
Solution: Number of Islands
Buildings With an Ocean View (medium)
Solution: Buildings With an Ocean View
Regular Expression Matching (hard)
Solution: Regular Expression Matching
First Missing Positive (hard)
Solution: First Missing Positive
Largest Rectangle in Histogram (hard)
Solution: Largest Rectangle in Histogram
Sliding Window Maximum (hard)
Solution: Sliding Window Maximum
Count Unique Characters of All Substrings of a Given String (hard)
Solution: Count Unique Characters of All Substrings of a Given String
Word Ladder (hard)
Solution: Word Ladder
Word Ladder II (hard)
Solution: Word Ladder II
Number of Flowers in Full Bloom (hard)
Solution: Number of Flowers in Full Bloom
Median of Two Sorted Arrays (hard)
Solution: Median of Two Sorted Arrays
Longest Valid Parentheses (hard)
Solution: Longest Valid Parentheses
Solution: Maximum Number of Balloons

Problem Statement

Given a string, determine the maximum number of times the word "balloon" can be formed using the characters from the string. Each character in the string can be used only once.

Examples:

  1. Example 1:

    • Input: "balloonballoon"
    • Expected Output: 2
    • Justification: The word "balloon" can be formed twice from the given string.
  2. Example 2:

    • Input: "bbaall"
    • Expected Output: 0
    • Justification: The word "balloon" cannot be formed from the given string as we are missing the character 'o' twice.
  3. Example 3:

    • Input: "balloonballoooon"
    • Expected Output: 2
    • Justification: The word "balloon" can be formed twice, even though there are extra 'o' characters.

Constraints:

  • 1 <= text.length <= 104
  • text consists of lower case English letters only.

Solution

To solve this problem, you start by creating a hashmap to count the frequency of each letter in the given string. Since the word "balloon" contains specific letters with varying frequencies (like 'l' and 'o' appearing twice), you need to account for these in your hashmap. Once you have the frequency of each letter, the next step is to determine how many times you can form the word "balloon". This is done by finding the minimum number of times each letter in "balloon" appears in the hashmap. The limiting factor will be the letter with the minimum frequency ratio to its requirement in the word "balloon". This approach ensures a balance between utilizing the available letters and adhering to the letter composition of "balloon".

  1. Character Frequency Count: Traverse the string and populate a hashmap with the frequency count of each character.

  2. Determine Maximum Count: Check the hashmap to determine the maximum number of times the word "balloon" can be formed. For characters 'b', 'a', and 'n', their frequency in the hashmap directly gives the number of times they can be used. For 'l' and 'o', we need to divide their frequency by 2.

  3. Result Calculation: The minimum value among the counts of 'b', 'a', 'l'/2, 'o'/2, and 'n' will give the maximum number of times the word "balloon" can be formed.

  4. Return the Result: Return the calculated minimum value as the final result.

This approach is effective because it ensures that we account for the frequency of each character required to form the word "balloon". Using a hashmap allows for efficient storage and retrieval of character frequencies.

Algorithm Walkthrough:

Given the input string "balloonballoooon":

  • Initialize an empty hashmap.
  • Traverse the string and populate the hashmap with character frequencies: {'b':2, 'a':2, 'l':4, 'o':5, 'n':2}.
  • Calculate the maximum number of times "balloon" can be formed:
    • 'b' can be used 2 times.
    • 'a' can be used 2 times.
    • 'l' can be used 4/2 = 2 times.
    • 'o' can be used 5/2 = 2.5 times, but since we need whole words, it's 2 times.
    • 'n' can be used 2 times.
  • The minimum among these values is 2, which is the final result.

Here is the visual representation of the algorithm:

Image

Code

Here is the code for this algorithm:

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity: The algorithm traverses the string once to populate the hashmap, which is O(n), where n is the length of the string. The subsequent operations are constant time. Therefore, the overall time complexity is O(n).

Space Complexity: The space complexity is determined by the hashmap, which in the worst case will have an entry for each unique character in the string. However, since the English alphabet has a fixed number of characters, the space complexity is O(1).

Maximum Number of Balloons (easy)
Binary Tree Path Sum (easy)
Mark as Completed

On this page

Problem Statement

Solution

Code

Complexity Analysis